import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    //根据二叉树创建字符串
    public String tree2str(TreeNode root) {
    StringBuilder sbu = new StringBuilder();
    tree2strChild(root,sbu);
    return sbu.toString();
    }
    public void tree2strChild(TreeNode root,StringBuilder sbu) {
        if (root == null){
            return;
        }
        sbu.append(root.val);
        if (root.left != null){
            sbu.append("(");
            tree2strChild(root.left, sbu);
            sbu.append(")");
        }else
            if (root.right!= null){
            sbu.append("()");
        }else{
                return;
            }
        if (root.right != null){
            sbu.append("(");
            tree2strChild(root.right, sbu);
            sbu.append(")");
        }else{
              return;
        }
    }
    //二叉树前序非递归遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list =new ArrayList<>();
        if (root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
       TreeNode cur = root;
       while (cur != null || !stack.isEmpty()){
          while (cur != null){
              stack.push(cur);
              list.add(cur.val);
              stack.push(cur.left);
          }
           TreeNode top = stack.pop();
           cur =top.right;
       }
        return  list;
    }
//二叉树的中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list =new ArrayList<>();
        if (root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);

                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur =top.right;
        }
        return  list;
    }
//二叉树的后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list =new ArrayList<>();
    if (root == null){
        return list;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    TreeNode prev = null;
    while (cur != null || !stack.isEmpty()){
        while (cur != null){
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode top = stack.peek();
        if (top.right == null ||top.right == prev){
            stack.pop();
            list.add(top.val);
            prev = top;
        }else{
            cur = top.right;
        }
    }
    return  list;
}
    //设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可
    public int[] smallestK(int[] arr, int k) {
        int[] sum = new int[k];
        Arrays.sort(arr);
        for(int i = 0; i < k ; i++){
            sum[i] = arr[i];
        }
        return sum;

    }


}